﻿#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

void swap(int* x, int* y) {
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

void HeapSortUp(int* arr, int n) {
	for (int i = 0; i < n; i++) {
		int child = i;
		int parent = (i - 1) / 2;
		while (child > 0) {
			if (arr[child] < arr[parent]) {
				swap(&arr[child],&arr[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else {
				break;
			}
		}
	}
	int end = n - 1;
	while (end) {
		swap(&arr[0], &arr[end]);
		end--;
		int parent = 0;
		int child = parent * 2 + 1;
		while (child < end) {
			if (child + 1 < end && arr[child] > arr[child + 1]) {
				child++;
			}
			if (arr[child] < arr[parent]) {
				swap(&arr[child], &arr[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else {
				break;
			}
		}
	}

}

void test01() {
	int arr[6] = { 3,5,2,6,1,4 };
	HeapSortUp(arr, 6);
	for (int i = 0; i < 6; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void HeapSortDown(int* arr, int n) {
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
		int parent = i;
		int child = i * 2 + 1;
		while (child < n) {
			if (child + 1 < n && arr[child + 1] < arr[child]) {
				child++;
			}
			if (arr[child] < arr[parent]) {
				swap(&arr[child], &arr[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else {
				break;
			}
		}
	}
	int end = n - 1;
	while (end > 0) {
		int parent = 0;
		int child = parent * 2 + 1;
		swap(&arr[0], &arr[end]);
		while (child < end) {
			if (child + 1 < end && arr[child] > arr[child + 1]) {
				child++;
			}
			if (arr[child] < arr[parent]) {
				swap(&arr[child], &arr[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else {
				break;
			}
		}
		end--;
	}
}
void test02() {
	int arr[6] = { 3,5,2,6,1,4 };
	HeapSortDown(arr, 6);
	for (int i = 0; i < 6; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}
int main() {
	//test01();
	test02();
	return 0;
}